package top.datacluster.basic.algorithm.leetcode.link;

/**
 * 面试题35. 复杂链表的复制
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 示例 2：
 *
 *
 *
 * 输入：head = [[1,1],[2,1]]
 * 输出：[[1,1],[2,1]]
 * 示例 3：
 *
 *
 *
 * 输入：head = [[3,null],[3,0],[3,null]]
 * 输出：[[3,null],[3,0],[3,null]]
 * 示例 4：
 *
 * 输入：head = []
 * 输出：[]
 * 解释：给定的链表为空（空指针），因此返回 null。
 *
 *
 * 提示：
 *
 * -10000 <= Node.val <= 10000
 * Node.random 为空（null）或指向链表中的节点。
 * 节点数目不超过 1000 。
 */
public class LeetCode1574 {

    public Node copyRandomList(Node head) {
        if (head == null){
            return null;
        }
        Node root = head;
        while (head != null){
            Node node = new Node(head.val);
            node.next = head.next;
            head.next = node;
            node.random = head.random;
            head = head.next.next;
        }
        head = root;
        while (head != null){
            if (head.next.random != null){
                head.next.random = head.random.next;
            }

            head = head.next.next;
        }
        head = root;
        Node copy = head.next;
        while (head != null){
            Node next = head.next.next;
            if (head.next.next != null){
                head.next.next = head.next.next.next;

            }
            head.next = next;
            head = next;
        }
        head = root;
        return copy;

    }

    public static void main(String[] args) {
        Node node1 = new Node(7);
        Node node2 = new Node(13);
        Node node3 = new Node(11);
        Node node4 = new Node(10);
        Node node5 = new Node(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node2.random = node1;
        node3.random = node5;
        node4.random = node2;
        node5.random = node1;
        new LeetCode1574().copyRandomList(node1);

    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}